package practise.sort.SortAlgrothim;


import com.sun.jndi.url.corbaname.corbanameURLContextFactory;

import java.util.Arrays;

/**
 * Created by richard on 5/11/14.
 */
public class QuickSort extends SortUtil {
    public static int[] sort(int[] arrays){
        int[] clone = arrays.clone();
        sort(clone,0,clone.length-1);
        return clone;
    }

    private static void sort(int[] array, int lo, int hi) {
        if(lo>=hi){
            return;
        }
        int num = array[lo];
        int left = lo+1;// actually, num index and left index always closed to each other
        int right = hi;
        int index=lo;
        while(left<=right){
            int compare = num - array[left];
            if(compare==0){
                left++;index++;//both can move to next
            }
            if(compare>0){ // if num > left, swap and both move to next
                swap(array,index++,left++);
            }
            else
                swap(array,left,right--);// only swap right, and right move back
        }
        sort(array,lo,index-1);
        sort(array,right+1,hi);
    }

}
